//
// Created by admin on 2020/7/17.
//

#include "demo.h"

SString StrInit(){
    char *ch = (char *)malloc(sizeof(char)*(MAXLEN+1));
    if (!ch){
        exit(0);
    }
    SString sString;
    sString.ch = ch;
    sString.length = 0;
    return sString;
}

void StrAssign(SString *S,char *chars,int length){
    S->length = strlen(chars);
    S->ch=chars;
}

Status StrCompar(SString S,SString T){
    if (S.length > T.length) return Greater;
    else if (S.length < T.length) return Less;
    else return Equal;
}

int StrLength(SString S){
    return S.length;
}

SString Concat(SString S,SString T){
    char *ch = (char *)malloc(sizeof(char)*(S.length+T.length));
    int i,j;
    for (i = 0; i < S.length; ++i) {
        ch[i] = S.ch[i];
    }
    for (j = 0; j < T.length; ++j) {
        ch[j+i] = T.ch[j];
    }
    SString sString = StrInit();
    sString.length = S.length+T.length;
    sString.ch = ch;
    return sString;
}

SString SubString(SString S,int postion,int length){
    if (postion < S.length){
        SString sString;
        int temp = postion;
        char *data = (char *)malloc(sizeof(char )*length);
        if ((postion+length) < S.length){
            for (int i = 0; i < length; ++i) {
                data[i] = S.ch[temp++];
            }
            sString.length = length;
        } else{
            for (int i = 0; i < S.length-postion; ++i) {
                data[i] = S.ch[temp++];
            }
            sString.length = S.length-postion;
        }
        sString.ch = data;
        return sString;
    } else{
        printf("Out Of Index!");
    }
}

SString StrCopy(SString S){
    SString sString;
    sString.ch = (char *)malloc(sizeof(char) * S.length);
    sString.length = S.length;
    for (int i = 0; i < S.length; ++i) {
        sString.ch[i] = S.ch[i];
    }
    return sString;
}

Bool StrEmpty(SString S){
    if (!S.length){
        return TRUE;
    } else{
        return FALSE;
    }
}

void ClearString(SString *S){
    if (!StrEmpty(*S)){
        S->length = 0;
    }
}

int Index_BF(SString S,SString T){
    int i = 0,j = 0;
    while (i<S.length && j<T.length){
        if (S.ch[i] == T.ch[j]){
            i++;
            j++;
        } else{
            i = i-j+1;
            j = 0;
        }
    }
    if (j==T.length){
        return i-T.length;
    }
    if (i==S.length){
        return -1;
    }
}

void Get_Next(SString S,int next[]){
    int i = 0,j = -1;
    next[0] = -1;
    while (i<S.length-1){
        if (j == -1 || S.ch[i] == S.ch[j]){
            i++;
            j++;
            //不优化
//            next[i] = j;
            //优化
            if (S.ch[i] != S.ch[j]){
                next[i] = j;
            } else{
                next[i] = next[j];
            }
        } else{
            j = next[j];
        }
    }
}

int Index_KMP(SString S,SString T,int next[]){
    int i = 0,j = 0;
    while (i<S.length && j<T.length){
        if (j == -1 || S.ch[i] == T.ch[j]){
            i++;
            j++;
        } else{
            j = next[j];
        }
    }
    if (j==T.length){
        return i-T.length;
    }
    if (i==S.length){
        return -1;
    }
}